#
# @lc app=leetcode.cn id=15 lang=python3
#
# [15] 三数之和
#
# https://leetcode-cn.com/problems/3sum/description/
#
# algorithms
# Medium (28.71%)
# Likes:    2422
# Dislikes: 0
# Total Accepted:    287K
# Total Submissions: 997.4K
# Testcase Example:  '[-1,0,1,2,-1,-4]'
#
# 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0
# ？请你找出所有满足条件且不重复的三元组。
#
# 注意：答案中不可以包含重复的三元组。
#
#
#
# 示例：
#
# 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
#
# 满足要求的三元组集合为：
# [
# ⁠ [-1, 0, 1],
# ⁠ [-1, -1, 2]
# ]
#
#
#

from typing import List
import time

# @lc code=start

# 2625 ms
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return[]

        result = []

        nums.sort()
        if nums[0] > 0 or nums[-1] < 0:
            return []

        for i in range(0, len(nums)):
            iMin = i + 1
            iMax = len(nums) - 1
            current = nums[i]
            if i != 0 and current == nums[i - 1]:
                i += 1
                continue
            while iMin < iMax:
                minimum = nums[iMin]
                maximum = nums[iMax]
                if iMin != i + 1 and minimum == nums[iMin - 1]:
                    iMin += 1
                    continue
                if iMax != len(nums) - 1 and maximum == nums[iMax + 1]:
                    iMax -= 1
                    continue
                if current + minimum + maximum == 0:
                    result.append([current, minimum, maximum])
                    iMin += 1
                    iMax -= 1
                if current + minimum + maximum < 0:
                    iMin += 1
                if current + minimum + maximum > 0:
                    iMax -= 1

        return result

# @lc code=end


start = time.time()
solution = Solution()
print(solution.threeSum([0, 0, 0, 0, 0, -1, -2, -3, 10]))
end = time.time()
print(start)
print(end)
print(end - start)

# timeout
# class Solution:
#     def threeSum(self, nums: List[int]) -> List[List[int]]:
#         negative = []
#         positive = []
#         twice = []
#         zero = 0
#         todo = dict()

#         for num in nums:
#             if num == 0:
#                 zero += 1
#             elif todo.get(num) == None:
#                 todo[num] = 1
#                 if num < 0:
#                     negative.append(num)
#                 else:
#                     positive.append(num)
#             elif todo[num] == 1:
#                 todo[num] = 2
#                 twice.append(num)

#         result = []

#         if len(negative) == 0 or len(positive) == 0:
#             if zero >= 3:
#                 return [[0, 0, 0]]
#             else:
#                 return []

#         if len(negative) >= 2:
#             for i in range(0, len(negative) - 1):
#                 for j in range(i + 1, len(negative)):
#                     for p in positive:
#                         n0 = negative[i]
#                         n1 = negative[j]
#                         if n0 + n1 + p == 0:
#                             result.append([n0, n1, p])

#         if len(positive) >= 2:
#             for i in range(0, len(positive) - 1):
#                 for j in range(i + 1, len(positive)):
#                     for n in negative:
#                         p0 = positive[i]
#                         p1 = positive[j]
#                         if p0 + p1 + n == 0:
#                             result.append([p0, p1, n])

#         if zero >= 3:
#             result.append([0, 0, 0])
#         if zero >= 1:
#             for n in negative:
#                 for p in positive:
#                     if n+p == 0:
#                         result.append([n, 0, p])

#         if len(twice) > 0:
#             for t in twice:
#                 for num in negative + positive:
#                     if num != t and t * 2 + num == 0:
#                         result.append([t, t, num])

#         return result

# timeout
# class Solution:
#     def threeSum(self, nums: List[int]) -> List[List[int]]:
#         if len(nums) < 3:
#             return []

#         results = []
#         zeroDic = {}

#         for i, ni in enumerate(nums):
#             for j, nj in enumerate(nums):
#                 if i >= j:
#                     continue
#                 for k, nk in enumerate(nums):
#                     if j >= k:
#                         continue

#                     if ni + nj + nk == 0:
#                         result = [ni, nj, nk]
#                         result.sort()

#                         if zeroDic.get(result[0]) == None:
#                             zeroDic[result[0]] = {result[1]: result[2]}
#                         elif zeroDic[result[0]].get(result[1]) == None:
#                             zeroDic[result[0]][result[1]] = result[2]

#         for k1, v1 in zeroDic.items():
#             for k2, v2 in v1.items():
#                 results.append([k1, k2, v2])

#         return results

# timeout
# class Solution:
#     def threeSum(self, nums: List[int]) -> List[List[int]]:
#         negative = []
#         positive = []
#         twice = []
#         todo = dict()
#         zero = 0

#         for num in nums:
#             if num == 0:
#                 zero += 1
#             count = todo.get(num)
#             if count == None:
#                 todo[num] = 1
#                 if num < 0:
#                     negative.append(num)
#                 else:
#                     positive.append(num)
#             elif count == 1 and num != 0:
#                 todo[num] = 2
#                 twice.append(num)

#         result = []

#         if len(negative) == 0 or len(positive) == 0:
#             if zero >= 3:
#                 return [[0, 0, 0]]
#             else:
#                 return []

#         if len(negative) >= 2:
#             for i, ni in enumerate(negative):
#                 for j, nj in enumerate(negative):
#                     if i >= j:
#                         continue
#                     opposite = (ni + nj) * -1
#                     if opposite in positive:
#                         result.append([ni, nj, opposite])

#         if len(positive) >= 2:
#             for i, pi in enumerate(positive):
#                 for j, pj in enumerate(positive):
#                     if i >= j:
#                         continue
#                     opposite = (pi + pj) * -1
#                     if opposite in negative:
#                         result.append([pi, pj, opposite])

#         if zero >= 3:
#             result.append([0, 0, 0])

#         noDup = negative + positive
#         if len(twice) > 0:
#             for t in twice:
#                 opposite = -1 * t * 2
#                 if opposite in noDup:
#                     result.append([t, t, opposite])

#         return result
